문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 하노이의 탑 (문단 편집) === [[스위프트(프로그래밍 언어)|Swift]] === import Foundation func hanoi(_ n: Int, from a: Int, to b: Int, by c: Int) { if n==1 { print("Move 1 from \(a) to \(b)") } else { hanoi(n-1, from: a, to: b, by: c) print("Move \(n) from\(a) to\(b)") hanoi(n-1, from: c, to: b, by: a) } } [youtube(FYCGV6F1NuY)] 재귀를 사용하지 않는 경우의 알고리즘은 다음과 같다. 원반의 총 개수를 [math(n)]이라 할 때 원반의 이동 회수는 위에서 언급한 대로 [math(2^n-1)]번이 되며, 각 회차를 [math(x)]라 할 때(1부터 [math(2^n-1)]까지) [math(x)]를 2진수로 표현하여 1이 들어가는 최저 자리수에 해당하는 원반을 왼쪽 또는 오른쪽으로 움직이면 된다. 3회차때는 11이므로 맨위의 1번 원반이, 16회차때는 1000의 4번 원반이 이동한다. 예를 들어 원반이 3개라면 1, 2, 3, 4, 5, 6, 7회차에 1번, 2번, 1번, 3번, 1번, 2번, 1번 이동하면 완성된다. 이 때 위에서부터 홀수번째의 원반이 왼쪽으로 이동(시프트, 더이상 왼쪽에 막대가 없다면 맨 오른쪽으로 이동)하면 짝수번째는 오른쪽으로 이동(마찬가지로 오른쪽 끝에서 오른쪽으로 가야 할 경우 왼쪽 끝으로 이동)하면 실수 없이 최소한으로만 움직일 수 있다. 이때 맨 위의 원반이 왼쪽과 오른쪽 가운데 어느 쪽으로 시프트하느냐에 따라 탑이 어느 막대로 움직이는가가 달라진다. 맨 위의 그림처럼 왼쪽 막대의 4개의 원반에 첫 원반이 오른쪽으로 간다면 마지막엔 오른쪽 막대에 정렬되며, 첫 원반이 왼쪽으로 가면 중앙 막대에 정렬된다. 퍼즐을 풀 때, 원반의 개수가 짝수라면 첫째 원반을 이동시킬 막대와는 다른 막대로 이동시켜야 한다. 홀수는 반대.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기